package jianzhi_offer;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class _53_字符流中第一个不重复的字符 {
    class Node{
        char val;
        Node pre;
        Node post;
        public Node(char val){
            this.val = val;
        }
    }
    Set<Character> set = new HashSet<>();
    Map<Character,Node> map = new HashMap<>();
    Node head = new Node(' ');
    Node tail = new Node(' ');

    public _53_字符流中第一个不重复的字符(){
        this.head.post = tail;
        this.tail.pre = head;
    }

    //Insert one char from stringstream
    public void Insert(char ch)
    {
        if(this.set.contains(ch)) return ;//已经有重复了的
        Node now = this.map.get(ch);
        if(now == null){//里面没有的
            now = new Node(ch);
            now.post = this.tail;
            now.pre = this.tail.pre;
            this.tail.pre.post = now;
            this.tail.pre = now;
            this.map.put(ch,now);
        }else{
            now.pre.post = now.post;
            now.post.pre = now.pre;
            this.map.remove(now);
            this.set.add(ch);
        }
    }
    //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
        if(this.head.post == this.tail) return '#';
        return this.head.post.val;
    }
}
